# -*- coding:utf-8 -*-
class Solution:
    '''
    搜索树左边小于根节点，右边大于根节点
    前序遍历：根节点，左子树，右子树
    中序遍历：左子树，根节点，右子树
    后序遍历：左子树，右子树，根节点
    '''

    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return 'No'
        root = sequence[-1]
        left = []
        right = []
        root_index = -1
        for i in range(len(sequence) - 1):
            if sequence[i] < root:
                left.append(sequence[i])
                root_index += 1
                if root_index < i:
                    return False
            else:
                right.append(sequence[i])
        left_res = True
        right_res = True
        if left:
            left_res = self.VerifySquenceOfBST(left)
        if right:
            right_res = self.VerifySquenceOfBST(right)
        if left_res  and right_res:
            return True
        else:
            return False
        # if not sequence:
        #     return None
        # root = sequence[-1]
        # index = -1
        # for i in range(len(sequence) - 1):
        #     if sequence[i] < root:
        #         index += 1
        #     else:
        #         break
        # for j in range(index + 1, len(sequence) - 1):
        #     if sequence[j] < root:
        #         return False
        # left = right = True
        # if index > 0:
        #     left = self.VerifySquenceOfBST(sequence[:index + 1])
        # if index < len(sequence) - 2:
        #     right = self.VerifySquenceOfBST(sequence[index + 1:-1])
        #
        # if left and right:
        #     return True
        # else:
        #     return False
test = Solution()
print(test.VerifySquenceOfBST([4,8,6,12,16,14,10]))